B20 - Edit Distance

提出

code: python

s = input()

t = input()

# dpij

dp = [0 * len(t) for _ in range(len(s))]

for i in range(len(s)):

for j in range(len(t)):

解答

code: python

s = input()

t = input()

dp = [0 * (len(t) + 1) for _ in range(len(s) + 1)]

for i in range(len(s)+1):

for j in range(len(t)+1):

if i >= 1 and j >= 1 and si-1 == tj-1:

# 上 + 1 or 左 + 1 or 左上 + 0/1

dpij = min(dpi-1j+1, dpij-1+1, dpi-1j-1)

elif i >= 1 and j >= 1:

dpij = min(dpi-1j+1, dpij-1+1, dpi-1j-1+1)

elif i >= 1:

dpij = dpi-1j+1

elif j >= 1:

dpij = dpij-1+1

メモ